{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 递归算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递归是一种解决问题的方法,将问题分解为更小的子问题,直到得到一个足够小的问题可以被很简单的解决。通常递归涉及函数调用自身。递归允许我们编写优雅的解决方案,解决可能很难编程的问题。为了了解递归编程，不妨先从二叉树讲起："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【１】二叉搜索树的创建"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给出一个数组alist = [21,28,14,32,25,18,11,30,19,15]，请编写一个算法按照下图示的过程那样创建一颗二叉树：\n",
    "\n",
    "<img src=\"image/chapter05/BST.gif\" width=400>\n",
    "\n",
    "从上面可以看出，树的根结点为数组的第一个数，随着后面的值不断插入，这棵树也不断成长。成长规则为：\n",
    "\n",
    "$\\bullet$ 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；<br>\n",
    "$\\bullet$ 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；<br>\n",
    "$\\bullet$ 任意节点的左、右子树也分别为二叉查找树；<br>\n",
    "$\\bullet$ 没有键值相等的节点。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先来定义一个子结点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,root,left=None,right=None):\n",
    "        self.root = root\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        return "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "然后开始创建树："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CreatTree(tree,value):\n",
    "    \n",
    "    if value>tree.root:\n",
    "        if tree.right is None:\n",
    "            tree.right = Node(value)\n",
    "        else:\n",
    "            CreatTree(tree.right,value)\n",
    "\n",
    "    if value<tree.root:\n",
    "        if tree.left is None:\n",
    "            tree.left = Node(value)\n",
    "        else:\n",
    "            CreatTree(tree.left,value)\n",
    "\n",
    "    return tree # 一定要返回　tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【２】理解 CreatTree 递归过程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "相信大家早就知道递归的实现是靠堆栈实现的，但是关于递归函数的参数和变量之间的关系却很模糊。为此,我写了几个不同的递归函数来分析它们之间有啥不同！并用一个 main 函数来分析："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def main(CreatTree,alist):\n",
    "    \n",
    "    try:   # 使用了一个 try 来处理异常。如果递归正确，那么返回　True;　否则返回 False\n",
    "        for i in range(len(alist)):\n",
    "            if i == 0:\n",
    "                tree=Node(alist[i])\n",
    "                continue\n",
    "            tree = CreatTree(tree,alist[i])\n",
    "\n",
    "        print('     ',tree.root)\n",
    "        print(' ',tree.left.root,'    ',tree.right.root)\n",
    "        print(tree.left.left.root,' ',\n",
    "              tree.left.right.root,tree.right.left.root,' ',tree.right.right.root)\n",
    "        return True\n",
    "    \n",
    "    except:\n",
    "        print(\" Recursion Error...\")\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先来看看我编写的 CreatTree 是否正确"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      21\n",
      "  14      28\n",
      "11   18 25   32\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist = [21,28,14,32,25,18,11,30,19,15]\n",
    "main(CreatTree,alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从上面可知，该函数运行正确！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CreatTree_１(tree,value):\n",
    "    \n",
    "    if value>tree.root:\n",
    "        if tree.right is None:\n",
    "            tree.right = Node(value)\n",
    "            return tree\n",
    "        else:\n",
    "            tree = CreatTree(tree.right,value) # tree = CreateTree(..) 会覆盖掉原来生成的树\n",
    "            \n",
    "\n",
    "    if value<tree.root:\n",
    "        if tree.left is None:\n",
    "            tree.left = Node(value)\n",
    "            return tree\n",
    "        else:\n",
    "            tree = CreatTree(tree.left,value)\n",
    "\n",
    "    return tree "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      19\n",
      " Recursion Error...\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " main(CreatTree_１,alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## N进制转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设你想将一个整数转换为一个二进制和十六进制字符串。例如,将整数10转换为十进制字符串表示为10,或将其字符串表示为二进制1010。虽然有很多算法来解决这个问题,包括在栈部分讨论的算法,但递归的解决方法非常优雅。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2进制:11101001\n",
      "3进制:22122\n",
      "4进制:3221\n",
      "5进制:1413\n",
      "6进制:1025\n",
      "7进制:452\n",
      "8进制:351\n",
      "9进制:278\n",
      "10进制:233\n",
      "11进制:1A2\n",
      "12进制:175\n",
      "13进制:14C\n",
      "14进制:129\n",
      "15进制:108\n",
      "16进制:E9\n"
     ]
    }
   ],
   "source": [
    "def divideByN(decNumber,N):\n",
    "    convertString = \"0123456789ABCDEF\"\n",
    "    if decNumber < N: # 如果输入值比 N 还小\n",
    "        return convertString[decNumber] # 那么相应的返回进制字符\n",
    "    \n",
    "    else:\n",
    "        # 否则继续整除，然后继续转换\n",
    "        return divideByN(decNumber//N,N) + convertString[decNumber%N]\n",
    "\n",
    "for N in range(2,17):\n",
    "    ans = divideByN(233,N)\n",
    "    print(\"{}进制:{}\".format(N,ans))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 探索迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "迷宫问题的根源与希腊的神话有关,传说忒修斯被送入迷宫中以杀死人身牛头怪。当忒修斯完成杀死野兽的任务，他用了一卷\n",
    "线帮助他找到回去的退路。在我们的问题中,我们将假设我们的乌龟在迷宫中间的某处,必须找到出路.\n",
    "\n",
    "<img src=\"image/chapter03/Screenshot from 2018-03-30 15-29-45.png\" width=300>\n",
    "\n",
    "为了使问题容易些,我们假设我们的迷宫被分成“正方形”。迷宫的每个正方形是开放的或被一段墙壁(用1表示)占据。乌龟只能通过迷宫的空心方块(用0表示)。如果乌龟撞到墙上,它必须尝试不同的方向。\n",
    "\n",
    "(1) 从我们的起始位置,我们将首先尝试向北一格,然后从那里递归地尝试我们的程序;<br>\n",
    "(2) 如果我们通过尝试向北作为第一步没有成功,我们将向南一格,并递归地重复我们的程序;<br>\n",
    "(3) 如果向南也不行,那么我们将尝试向西一格,并递归地重复我们的程序;<br>\n",
    "(4) 如果北,南和西都没有成功,则应用程序从当前位置递归向东;<br>\n",
    "(5) 如果这些方向都没有成功,那么没有办法离开迷宫,我们失败。<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [1, 2, 0, 0, 1, 1, 0, 0, 2, 2, 2, 2, 2, 1],\n",
       " [1, 2, 1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 1],\n",
       " [1, 2, 1, 0, 1, 1, 1, 1, 2, 1, 0, 1, 2, 1],\n",
       " [1, 2, 1, 0, 0, 0, 0, 0, 2, 1, 1, 1, 2, 1],\n",
       " [1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 0, 0, 2, 1],\n",
       " [1, 2, 1, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2, 1],\n",
       " [1, 2, 0, 2, 1, 1, 1, 0, 1, 0, 1, 1, 2, 1],\n",
       " [1, 2, 1, 2, 1, 0, 1, 0, 1, 0, 1, 0, 2, 1],\n",
       " [1, 2, 1, 2, 1, 0, 1, 0, 1, 0, 0, 1, 2, 1],\n",
       " [1, 2, 2, 2, 0, 0, 1, 0, 0, 1, 0, 2, 2, 1],\n",
       " [1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 2, 1, 1],\n",
       " [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 1, 1],\n",
       " [1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 2, 2, 0, 1],\n",
       " [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from copy import deepcopy\n",
    "from queue import Queue\n",
    "\n",
    "maze = [\n",
    "        [1,0,1,1,1,1,1,1,1,1,1,1,1,1],\n",
    "        [1,0,0,0,1,1,0,0,0,0,0,0,0,1],\n",
    "        [1,0,1,0,0,0,0,1,0,1,0,1,0,1],\n",
    "        [1,0,1,0,1,1,1,1,0,1,0,1,0,1],\n",
    "        [1,0,1,0,0,0,0,0,0,1,1,1,0,1],\n",
    "        [1,0,1,1,1,1,1,1,0,1,0,0,0,1],\n",
    "        [1,0,1,0,0,0,0,0,0,0,1,1,0,1],\n",
    "        [1,0,0,0,1,1,1,0,1,0,1,1,0,1],\n",
    "        [1,0,1,0,1,0,1,0,1,0,1,0,0,1],\n",
    "        [1,0,1,0,1,0,1,0,1,0,0,1,0,1],\n",
    "        [1,0,0,0,0,0,1,0,0,1,0,0,0,1],\n",
    "        [1,0,1,1,1,0,1,1,0,1,1,0,1,1],\n",
    "        [1,0,0,0,1,0,0,0,1,0,1,0,1,1],\n",
    "        [1,1,1,0,0,1,1,0,1,0,0,0,0,1],\n",
    "        [1,1,1,1,1,1,1,1,1,1,0,1,1,1]]\n",
    "\n",
    "\n",
    "paths = ([1,0],[-1,0],[0,1],[0,-1]) # 表示东西南北四个方向\n",
    "answer = Queue() # 用一个队列来存储能够成功走出来的路径\n",
    "answer.put((0,1))# 起始路径入队列\n",
    "\n",
    "def find_path(maze,pos):\n",
    "    \n",
    "    maze = deepcopy(maze)\n",
    "    global path,answer\n",
    "    # 标记该乌龟现在的位置已走过，用 2 表示\n",
    "    maze[pos[0]][pos[1]] = 2\n",
    "    # 如果该位置为出口，那么打印足迹，返回 True\n",
    "    if pos[0] == 14  and pos[1] == 10: return True\n",
    "    \n",
    "    # 不是出口，则遍历东南西北四个方向\n",
    "    for path in paths:\n",
    "        i,j = pos[0]+path[0],pos[1]+path[1]\n",
    "        # 寻找可以行走的路\n",
    "        if maze[i][j] !=0:\n",
    "            continue\n",
    "            \n",
    "        # 现在判断该方向能不能通往出口\n",
    "        if find_path(maze,[i,j]):\n",
    "            # 如果能的话，标记该位置走过\n",
    "             maze[i][j] = 2\n",
    "             answer.put((i,j)) # 位置入队列\n",
    "             return True\n",
    "    \n",
    "    return False\n",
    "\n",
    "find_path(maze,[0,1])\n",
    "while not answer.empty():\n",
    "    path = answer.get()\n",
    "    i,j = path\n",
    "    maze[i][j] = 2\n",
    "\n",
    "maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 八皇后问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任何两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题：这时棋盘的大小变为 n×n，而皇后个数也变成 n。当且仅当 n = 1 或 n ≥ 4 时问题有解。\n",
    "\n",
    "\n",
    "<img src=\"image/chapter03/queue.jpeg\" width = 300>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8, 1, 1, 1, 1, 1, 1, 1]\n",
      "[1, 1, 1, 1, 8, 1, 1, 1]\n",
      "[1, 1, 1, 1, 1, 1, 1, 8]\n",
      "[1, 1, 1, 1, 1, 8, 1, 1]\n",
      "[1, 1, 8, 1, 1, 1, 1, 1]\n",
      "[1, 1, 1, 1, 1, 1, 8, 1]\n",
      "[1, 8, 1, 1, 1, 1, 1, 1]\n",
      "[1, 1, 1, 8, 1, 1, 1, 1]\n",
      "Success!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from copy import deepcopy\n",
    "\n",
    "def Put(chess,pos):\n",
    "    \"\"\"\n",
    "    在棋盘 pos 位置上放了一个皇后，棋盘发生了改变：\n",
    "    该皇后同一横行、纵行或斜线上的位置都标记为 1 ，\n",
    "    表示不可以摆放其他皇后了。\n",
    "    \"\"\"\n",
    "    [m,n] = pos\n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            if abs(i-m) in (0,abs(j-n)) or abs(j-n)==0:\n",
    "                chess[i][j] = 1\n",
    "    return chess\n",
    "\n",
    "def mark(chess,pos,flag):\n",
    "    \"\"\"\n",
    "    棋盘 pos 位置上放了一个皇后(标记为 8 )，并且用\n",
    "    flag 来记录已经放置在棋盘上的皇后数目。\n",
    "    \"\"\"\n",
    "    chess = Put(chess,pos)\n",
    "    flag += 1\n",
    "    [m,n] = pos\n",
    "    chess[m][n] = 8\n",
    "    return flag\n",
    "\n",
    "def find_path(chess,pos,flag):\n",
    "    chess = deepcopy(chess)  # 进行传参并复制，以免改变原来的棋盘\n",
    "    flag = mark(chess,pos,flag) # 放置皇后，并标记和记录\n",
    "    if flag == N:\n",
    "        for n in range(len(chess)):\n",
    "            print(chess[n])\n",
    "        print(\"Success!\")\n",
    "        return True\n",
    "    \n",
    "    # 遍历棋盘上可以放置皇后的位置\n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            if chess[i][j] == 0:\n",
    "                # 如果可以成功，那么返回True， 否则继续遍历\n",
    "                if find_path(chess,[i,j],flag):\n",
    "                    pos = [i,j]\n",
    "                    flag = mark(chess,pos,flag)\n",
    "                    return True\n",
    "    return False\n",
    "\n",
    "N = 8 # \n",
    "chess = [[0]*N for i in range(N)]\n",
    "find_path(chess,[0,0],0)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
